Search results for "Independent set"

The directed profitable rural postman problem with incompatibility constraints

2017

[EN] In this paper, we study a variant of the directed rural postman problem (RPP) where profits are asso- ciated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers …

Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs

2009

AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.

On the chromatic number of disk graphs

1998

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.

Remarks on Partially Square Graphs, Hamiltonicity and Circumference

2001

Pattern Matching and Pattern Discovery Algorithms for Protein Topologies

2001

We describe algorithms for pattern-matching and pattern-learning in TOPS diagrams (formal descriptions of protein topologies). These problems can be reduced to checking for subgraph isomorphism and finding maximal common subgraphs in a restricted class of ordered graphs. We have developed a subgraph isomorphism algorithm for ordered graphs, which performs well on the given set of data. The maximal common subgraph problem then is solved by repeated subgraph extension and checking for isomorphisms. Despite its apparent inefficiency, this approach yields an algorithm with time complexity proportional to the number of graphs in the input set and is still practical on the given set of data. As a…

A smallest irregular oriented graph containing a given diregular one

2004

AbstractA digraph is called irregular if its vertices have mutually distinct ordered pairs of semi-degrees. Let D be any diregular oriented graph (without loops or 2-dicycles). A smallest irregular oriented graph F, F=F(D), is constructed such that F includes D as an induced subdigraph, the smallest digraph being one with smallest possible order and with smallest possible size. If the digraph D is arcless then V(D) is an independent set of F(D) comprising almost all vertices of F(D) as |V(D)|→∞. The number of irregular oriented graphs is proved to be superexponential in their order. We could not show that almost all oriented graphs are/are not irregular.

Partially Square Graphs, Hamiltonicity and Circumference II

2000

Abstract Given a graph G, its partially square graph G∗ is a graph obtained by adding an edge uv for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition NG(x) ⊆ NG[u] ∪ NG[v], where NG[x]= NG(x) ∪ {x}. In case G is a claw-free graph, G∗ is equal to G2, We define σ ∗ t = min{ ∑ x∈ d ∗ G (x): S is an independent set in G ∗ and ∣S∣ = t} , where d ∗ G (x) = ∣{y ∈ V∣ xy ∈ E(G∗)}∣ . We give for hamiltonicity and circumference new sufficient conditions depending on and we improve some known results.

Some properties of vertex-oblique graphs

2016

The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…

On the hardness of optimization in power-law graphs

2008

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

2008

Graphs and Algorithms